Time

• The tables we discussed last week represent games where each player moves once, and those moves are simultaneous.
• But few games are like that.
• We need a way to represent games that take time.

Trees

• We do that with trees.
• A tree represents all the ways that a game that takes place over time could go.

Nodes

• Trees have nodes.
• Some nodes are terminal nodes; they represent that the game has ended.
• Each terminal node has a payout for each of the players.
• At any other node, either a player moves, or Nature ‘moves’.
• One of the non-terminal nodes is special: it is the node where the game starts.

Branches

• Each non-terminal node has branches, leading to other nodes.
• A move at a node is always a choice of branches.

Future Additions

• Moves by Nature
• Moves under uncertainty

Class of Games We’re Discussing

• Two-player
• Turn-taking
• Finite
• No hidden facts
• No randomness
• We’ll start with zero-sum games, though drop this later.

Five

• There are two players, who we’ll call A and B.
• First A moves, then B, then finally A moves again.
• Each move involves announcing a number, 1 or 2.
• A wins if after the three moves, the numbers announced sum to 5.
• B wins otherwise.

Five

Question: How should you play this game?

Solving These Games

• Work backwards.
• First, find points where a player has a choice between two terminal nodes.
• Assume that they will make the higher value for them choice.
• Mark that choice, e.g., by doubling the line (as the textbook does).
• If there are ties, mark both of the lines. (This gets more complicated once we leave zero-sum games.)

Solving These Games

• Assign the value they choose to the choice node.
• So just the game assigns values to terminal nodes, we’ll now assign value to choice nodes.
• In Five, we’ll assign the value \(W\) to the bottom right node.

Five (after one step)

Next Steps Back

• Now we do the same thing for B.
• We act as if B is choosing between terminal nodes.
• It is as if A doesn’t have a choice - they will just make the choice that is best for them (i.e., worst for B).
• So B knows what the outcome of each choice will be.

Five (After Two Rounds)

• So we act as if getting to the left hand node means B wins, and getting to the right hand node means A wins.
• And now we just have to make the choice for the initial node, using this fact.

Five - Full Analysis

• The equilibrium state of the game is that A wins.
• A plays 2 first.
• Then B can play anything they line.
• But whatever they do, A will win, by playing the opposite number.

Backwards Induction

• This process is called backwards induction.
• We start at the possible ends of the game.
• At each step, we assume that each player makes the best decision they can, on the assumption that later players will do the same thing.

Backwards Induction in Positive Sum Games

Multiple Solutions

• This is a game with multiple backwards induction solutions.
• The solutions don’t just differ in what Player 3, who faces the tie, plays.
• They differ in the very first move!

Multiple Solutions

• This is the totally general case; most solution concepts are like this.
• But it’s a pain to deal with.
• And eventually we can solve the game.